#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include <string.h>
#include "../include/filedesc.h"
#include "../include/bst.h"




/* Function for creating bst */
b_node *bst_create()
{
	b_node *new_node = NULL;
	return new_node;
}	

//char buffer[100];


void replace(char str[], char from[], char to[])
{
	char str2[strlen(str)];
	strcpy(str2,str);
	strcpy(strstr(str2,from), to);
	strcat(str2,str + strlen(str2)+ strlen(from) - strlen(to));
	strcpy(str, str2);
}

/*void replace1(char str[],char from[],char to[])
{

	 	



}*/
/*Function for insertion of node in bst tree */
int bst_insert ( b_node **bst_root_ptr, fd *data )
{
	 b_node *curr_node = NULL;
	 int slot_found,i;
	 char full_path[300], newstr;
         if(strcmp(data->file_name,"/")==0)
                 strcpy(full_path,"/");
                     
        else{
          if(strcmp(data->path,"/")==0){
              strcpy(full_path,data->path);
            //strcat(full_path,"/");
            strcat(full_path,data->file_name);
            }
           else{

             strcpy(full_path,data->path);
             strcat(full_path,"/");
             strcat(full_path,data->file_name);
            }
      
}
	//printf("%s->the node to be inserted in bst\n",full_path);
	b_node *new_node = (b_node*) malloc( sizeof(b_node) );
	if( new_node == NULL ){
		fprintf(stderr, "bst_create_node: Unable to allocate memory\n");
		exit(0);
	}
	strcpy(new_node->full_path,full_path);
       //rintf("%s->full path\n",new_node->full_path);
	new_node->file_desc =data;
	new_node->parent = NULL;
	new_node->left = NULL;
	new_node->right = NULL;

	if( *bst_root_ptr == NULL ){
		*bst_root_ptr = new_node;
		
	}
	else{
		slot_found = BST_FALSE;
		curr_node = *bst_root_ptr;
		while( !slot_found ){
			if( strcmp( full_path ,curr_node->full_path) == 0 )
			{
				//fprintf(stderr, "bst_insert: Duplicate Path %s ignored\n", full_path);
				slot_found = BST_TRUE;
				return 1;
			}
	  	   else if( strcmp(curr_node->full_path,full_path) > 0 )
			{
				if( curr_node->left != NULL )
				{
					slot_found = BST_FALSE;
					curr_node = curr_node->left;
				}
				else{
					slot_found = BST_TRUE;
					curr_node->left = new_node;
					new_node->parent = curr_node;
				}
			}
		  else{ /* that is, key > curr_node->key */
				if( curr_node->right != NULL )
				{
					slot_found = BST_FALSE;
					curr_node = curr_node->right;
				}
				else{
					slot_found = BST_TRUE;
					curr_node->right = new_node;
					new_node->parent = curr_node;
				}
		   }
		}
	}
	return 0;
}
	
/*Function for serching the bst tree */
b_node *bst_search( b_node *bst_root, char *full_path )
{
	b_node *curr_node;
	int slot_found;

	if( bst_root == NULL )
	{
		//fprintf( stderr, "bst_search: Tree does not exist\n" );
		return NULL;
   	}
	else
	{
		slot_found = BST_FALSE;
		curr_node = bst_root;
		while( !slot_found )
		{
			if( strcmp( full_path ,curr_node->full_path) == 0  ){
				
				slot_found = BST_TRUE;
			}
			else if( strcmp(curr_node->full_path,full_path) > 0 ){
				if( curr_node->left != NULL ){
					slot_found = BST_FALSE;
					curr_node = curr_node->left;
				}
				else{
					//fprintf(stderr, "BST: Path %s not found in tree", full_path);
					return NULL;
				}
			}
			else
			{ 
				if( curr_node->right != NULL ){
					slot_found = BST_FALSE;
					curr_node = curr_node->right;
				}
				else{
					//printf("here alos");
					//fprintf(stderr, "BST: Path %s not found in tree", full_path);
					return NULL;
				}
			}
	 	}
           
		if( slot_found )
		{	
			//fd* f = (fd*)curr_node->file_desc;
			return curr_node;
		
		}
		else{
			//fprintf(stderr, "BST: Path %s not found in tree", full_path);
			return NULL;
		}
	}	

}

		


/*char replace1(char *str1, char str[])
{
	strcat(str1,str);
        return str;
}
*/


/*Function for deleting the node of tree */
int bst_delete(b_node **bst_root_ptr,char *fullpath)
{       char fullp[300];
        int i;
	b_node *temp;
  	b_node *papa,*x,*xsucc;
	if(bst_root_ptr==NULL)
	{
		//printf("\ntree is empty\n");
		return 1;
	}
	papa=x=NULL;
	
        for(i=0;i<strlen(fullpath)-1;i++){
	   fullp[i]=fullp[i+1];
	
        }
	x=bst_search(*bst_root_ptr,fullpath);
	
	if(x==NULL)
	{
		//printf("\nNode for deletion not found\n");
		return 1;
	}

	if(x->left!=NULL && x->right!=NULL)
	{
		papa=x;
		xsucc=x->right;
		while(xsucc->left!=NULL)
		{
			papa=xsucc;
			xsucc=xsucc->left;
		}
		strcpy(x->full_path,xsucc->full_path);
		x->file_desc=xsucc->file_desc;
                
		x=xsucc->right;
//x=xsucc;
//temp=xsucc->parent;
//temp->left=NULL;
	}
	
	papa=x->parent;
	if(x->left==NULL && x->right==NULL)
	{
		if(x == *bst_root_ptr)
		{
			x=NULL;
			return 0;
		}	
		
		if(papa->right==x)
			papa->right=NULL;
		else
			papa->left=NULL;
			return 0;
	}

	if(x->left==NULL && x->right!=NULL)
	{
		if(x == *bst_root_ptr)
		{
			*bst_root_ptr=x->right;
			x=NULL;
			return 0;
		}	
		
		if(papa->left==x)
			papa->left=x->right;
		else
			papa->right=x->right;
		return 0;
	}
	

	if(x->left!=NULL && x->right==NULL)
	{
		if(x == *bst_root_ptr)
		{
			*bst_root_ptr=x->left;
			x=NULL;
			return 0;
		}	
				
		if(papa->left==x)
			papa->left=x->left;
		else
			papa->right=x->left;
		return 0;
	}
	
	return 1;
}	
	
	
	
	
/*Function for printing the bst tree in inorder */
void print_inorder(b_node *bst_root)
{
	
	if(bst_root != NULL)
    {
     	print_inorder(bst_root->left);
        fd* f = (fd*)bst_root->file_desc;
        printf("\nName : %s", f->file_name); 	
        printf("\tFull Path%s\n",bst_root->full_path);
        print_inorder(bst_root->right);
   }
   
} 	


